//
// Created by zhou on 2021/10/23.
//
//先使用深度优先搜索的方式
//然后再使用广度优先搜索
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    const int dx[4]={0,0,-1,1};
    const int dy[4]={1,-1,0,0};
    void DFS(vector<vector<int>>& image,int sr,int sc,int curColor,int newColor){
        if(image[sr][sc]==curColor){
            image[sr][sc]=newColor;
            for(int i=0;i<4;i++){
                int mx=dx[i]+sr;
                int my=dy[i]+sc;
                if(mx>=0&&mx<image.size()&&my>=0&&my<image[0].size()){
                    DFS(image,mx,my,curColor,newColor);
                }
            }
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int currColor=image[sr][sc];
        if(currColor!=newColor){
            DFS(image,sr,sc,currColor,newColor);
        }
        return image;
    }
    vector<vector<int>> floodFill1(vector<vector<int>>& image, int sr, int sc, int newColor){
        int curcolor=image[sr][sc];
        if(curcolor==newColor)return image;
        queue<pair<int,int>> que;
        int n=image.size(),m=image[0].size();
        que.emplace(make_pair(sr,sc));

        while(!que.empty()) {
            int x = que.front().first;
            int y = que.front().second;
            image[x][y] = newColor;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int mx = dx[i] + x;
                int my = dy[i] + y;
                if (mx >= 0 && mx < n && my >= 0 && my < n && image[mx][my] == curcolor) {
                    que.emplace(make_pair(mx, my));
                }
            }
        }
            return image;
        }

};



int main(){
    Solution solution;
    vector<vector<int>> nums={{1,1,1,0,1},
                              {1,1,0,1,0},
                              {1,1,0,0,1},
                              {0,0,1,0,0},
    };
    solution.floodFill1(nums,1,1,10);
    for(auto i:nums){
        for(auto j:i){
            cout<<j<<",";
        }
        cout<<endl;
    }
}